//环路检测
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* slow=head, *fast=head;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                ListNode* ptr=head;
                while(ptr!=slow)
                {
                    ptr=ptr->next;
                    slow=slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
        
    }
};
//把字符串转换成整数
class Solution {
public:
    int strToInt(string str) 
    {
        int flag=1;
        int l=str.size();
        int i=0;
        long long res=0;
        while(i<l && str[i]==' ') i++;
        if(str[i]=='-' || str[i]=='+') 
        {
            flag=str[i]=='-'?-1:1;
            i++;
        }
        if(str[i]<'0' || str[i]>'9') return 0;
        while(i<l)
        {
            if(str[i]<'0' || str[i]>'9') break;
            res=res*10;
            res+=str[i]-'0';
            i++;
            if(res>INT_MAX && flag==1) 
            {
                return INT_MAX;
            }
            else if(res> INT_MAX && flag==-1)
            {
                return INT_MIN;
            }
        }
        return flag*res;
    }
};
// 移除重复节点
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) 
    {
        set<int> m;
        ListNode* cur=head;
        ListNode* pre=nullptr;
        while(cur)
        {
            //如果不在m里面
            if(m.find(cur->val)==m.end())
            {
                m.insert(cur->val);
                pre=cur;
            }
            else
            {
                //cur所代表的节点已经存在 删除cur节点
                pre->next=cur->next;
            }
            cur=cur->next;
        }
        
        return head;
    }
};

//加减的目标值

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        // 假设nums的总和为sum
        // 正数的和为 sumA 负数的和为 sum-sumA
        // sumA - (sum-sumA)=target  sumA= (target+sum)/2
        //所以需要求的是 能将背包容量为sumA的背包装满有几种方法
        int sum=0;
        for(auto e:nums) sum+=e;
        if(sum<target) return 0;
        if((target+sum)%2 != 0) return 0;
        int m=(target+sum)/2;
        vector<int>dp(m+1,0);
        dp[0]=1;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=m;j>=nums[i];j--)
            {
                dp[j]=dp[j]+dp[j-nums[i]];
            }
        }
        return dp[m];
    }
};
//小行星碰撞

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) 
    {
        stack<int> st;
        for(int i=0;i<asteroids.size();i++)
        {
            // 一直摧毁栈顶为正的元素 直到栈为空 
           while(!st.empty() && st.top()>0 && st.top() < -asteroids[i])
           {
               st.pop();
           }
           //走到这里 要么栈顶为负数 要么栈空
           //要么i号陨石小于等于栈顶元素的绝对值 或者 i号压根为正的
           if(!st.empty() && asteroids[i]<0 &&st.top()==-asteroids[i])
           {
               st.pop();
           }
           else if(asteroids[i]>0 || st.empty() || st.top()<0)
           {
               st.push(asteroids[i]);
           }
        }
        vector<int>res(st.size(),0);
        for(int i=st.size()-1;i>=0;i--)
        {
            res[i]=st.top();
            st.pop();
        }
        return res;
    }
};